#ifndef _MY_QUEUE_TCC_
#define _MY_QUEUE_TCC_

template<typename T>
void my_queue<T>::increaseExternalCount(atomic<countedNodePtr>& counter, countedNodePtr& oldCounter) {
	countedNodePtr newCounter;
	do {
		newCounter = oldCounter;
		++newCounter.externalCount;
	} while (!counter.compare_exchange_strong(oldCounter, newCounter));
	oldCounter.externalCount = newCounter.externalCount;
}

template<typename T>
void my_queue<T>::freeExternalCounter(countedNodePtr& oldNodePtr) {
	node* const ptr = oldNodePtr.ptr;
	const int k = oldNodePtr.externalCount - 2;
	nodeCounter oldCounter = ptr->count.load();
	nodeCounter newCounter;
	do {
		newCounter = oldCounter;
		--newCounter.externalCounters;
		newCounter.internalCount += k;
	} while (ptr->count.compare_exchange_strong(oldCounter, newCounter));
	if (!newCounter.externalCounters && !newCounter.internalCount) {
		delete ptr;
	}
}

template<typename T>
void my_queue<T>::setNewTail(countedNodePtr& oldTail, const countedNodePtr& newTail) {
	node* const ptr = oldTail.ptr;
	while (!tail.compare_exchange_weak(oldTail, newTail) && ptr == oldTail.ptr);
	if (ptr == oldTail.ptr) {
		freeExternalCounter(oldTail);
	} else {
		ptr->releaseRef();
	}
}

template<typename T>
void my_queue<T>::push(const T& data) {
	unique_ptr<T> newData = unique_ptr<T>(new T(data));
	countedNodePtr newNext;
	newNext.ptr = new node;
	newNext.externalCount = 1;
	countedNodePtr oldTail = tail.load();
	for (;;) {
		increaseExternalCount(tail, oldTail);
		T* oldData = nullptr;
		if (oldTail.ptr->data.compare_exchange_strong(oldData, newData.get())) {
			countedNodePtr oldNext = {0};
			if (!oldTail.ptr->next.compare_exchange_strong(oldNext, newNext)) {
				delete newNext.ptr;
				newNext = oldNext;
			}
			setNewTail(oldTail, newNext);
			newData.release();
			break;
		} else {
			countedNodePtr oldNext = {0};
			if (oldTail.ptr->next.compare_exchange_strong(oldNext, newNext)) {
				oldNext = newNext;
				newNext.ptr = new node;
			}
			setNewTail(oldTail, oldNext);
		}
	}
}

template<typename T>
unique_ptr<T> my_queue<T>::pop() {
	countedNodePtr oldHead = head.load();
	for (;;) {
		increaseExternalCount(head, oldHead);
		node* const ptr = oldHead.ptr;
		if (ptr == tail.load().ptr) {
			return unique_ptr<T>();
		}
		countedNodePtr next = ptr->next.load();
		if (!head.compare_exchange_strong(oldHead, next)) {
			T* const result = ptr->data.exchange(nullptr);
			freeExternalCounter(oldHead);
			return unique_ptr<T>(result);
		}
		ptr->releaseRef();
	}
}

#endif
